package top.kiterunner.learning.data_structure;

import java.util.Arrays;

/**
 * AdorynZhao in Tencent-UESTC.
 * Source Code Created on 2017/7/4.
 */
public class SortAlgoDemo {

    private static void printArray(int[] array) {
        for (int e : array) {
            System.out.print(" " + e);
        }

        System.out.println();
    }

    private static void swap(int[] num, int index1, int index2) {
        int trf = num[index1];
        num[index1] = num[index2];
        num[index2] = trf;
    }

    /*
    冒泡排序的过程（升序）：
    比较相邻的元素，如果第一个比第二个大，交换它们。
    对每一对相邻元素都这样做，到最后就是，最后的元素就是最大的。
    后续依次进行，每次循环不处理最后一个。
    */
    public static void bubbleSort(int[] number) {
        int len = number.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - 1 - i; j++) {
                if (number[j] > number[j + 1])
                    swap(number, j, j + 1);
            }
        }
    }

    /*
    选择排序的过程（升序）：
    在一组要排序的元素中，选择最小的元素与第一个元素进行交换，然后，在选择次小的元素与第二个元素交换，依次进行。
    */
    public static void selectSort(int[] numbers) {
        int len = numbers.length;
        for (int i = 0; i < len - 1; i++) {
            int min = i;
            for (int j = i + 1; j < len; j++) {
                min = (numbers[min] < numbers[j]) ? min : j;
            }
            swap(numbers, min, i);
        }
    }

    /*
    插入排序的过程（升序）：
    前面的元素维持升序状态，后面的元素依次按序插入前面的序列之中。
    */
    public static void insertSort(int[] numbers) {
        int len = numbers.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (numbers[j] < numbers[j - 1])
                    swap(numbers, j, j - 1);
                else
                    break;
            }
        }
    }

    public static void main(String[] args) {

        int[] ns = {12, 11, 8, 9, 22, 18};
        int[] ns2 = Arrays.copyOf(ns, ns.length);
        Arrays.sort(ns);
        printArray(ns);

        // bubbleSort(ns2);
        //selectSort(ns2);
        insertSort(ns2);
        printArray(ns2);
    }
}
